Rahman memainkan peranan dalam pembentukan Parti Negara Sarawak (PANAS) dan Barisan Ra'ayat Jati Sarawak (BARJASA) dengan membantu dalam penggubalan perlembagaan kedua-dua pihak. Walau bagaimanapun, Rahman memutuskan untuk menyertai BARJASA kerana beliau menentang golongan bangsawan Melayu di PANAS. Rahman bertanding dalam 1963 pilihan raya kerajaan tempatan di Sarawak tetapi telah dikalahkan bersama-sama dengan ahli-ahli partinya seperti Ustaz Abdul Kadir Hassan dan Suut Haji Tahir. Kerajaan persekutuan Malaysia mencalonkan Abdul Rahman sebagai Ketua Menteri Sarawak yang pertama. Walau bagaimanapun, pencalonannya ditolak oleh Perikatan Sarawak yang telah dikuasai oleh Parti Kebangsaan Sarawak (SNAP) parti itu.

Menteri di dalam kabinet persekutuan

Rahman telah dipilih oleh Majlis Negeri (kini Dewan Undangan Negeri Sarawak) untuk menjadi ahli parlimen pada bulan Oktober 1963. Beliau kemudian dilantik sebagai Penolong Menteri Persekutuan Pembangunan Negara dan Luar Bandar Sarawak. Perdana Menteri Malaysia yang pertama, Tunku Abdul Rahman membawa Abdul Rahman ke dalam politik manakala Perdana Menteri yang kedua, Tun Abdul Razak menjadi mentor beliau. Tunku berpuas hati dengan prestasi Abdul Rahman sebagai menteri persekutuan. Rahman kemudiannya dinaikkan pangkat sebagai menteri penuh Tanah dan Galian pada tahun 1965. Rahman mula mengesyorkan kerajaan persekutuan dengan menubuhkan syarikat minyak negara yang kemudiannya dikenali sebagai Petronas pada tahun 1974. Beliau juga mencadangkan supaya Tengku Razaleigh Hamzah dilantik sebagai pengerusi Petronas.

Rahman menjadi Menteri Pelajaran pada tahun 1969. Beliau membuat langkah berani dengan menukar bahasa pengantar untuk semua sekolah-sekolah dan institusi pengajian tinggi dari Bahasa Inggeris ke bahasa Melayu. Beliau juga ingin mewujudkan Universiti Kebangsaan Malaysia (UKM) pada tahun 1970. Menteri Pelajaran adalah portfolio terakhir Rahman sebelum beliau kembali ke Sarawak.